package com.zhj.leetcode;

/**
 * 力扣200 岛屿数量
 */
public class Test200 {
    public static void main(String[] args) {
        // 这是一片大陆，横竖连载一块的属于一个岛屿，本片大陆有三个岛屿
        int[][] grid = {
                {1, 1, 0, 0, 0},
                {1, 1, 0, 0, 0},
                {0, 0, 1, 0, 0},
                {0, 0, 0, 1, 1}
        };
        System.out.println(getSum(grid));
    }

    public static int getSumDFS(int[][] grid) {
        if (grid == null) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    sum++;
                    dfs(grid, i, j, grid.length, grid[i].length);
                }
            }
        }
        return sum;
    }

    /**
     * 占领岛屿
     * @param grid
     * @param x
     * @param y
     * @param row
     * @param col
     */
    private static void dfs(int[][] grid, int x, int y, int row, int col) {
        if (x<0 || y<0 || x>= row || y >= col || grid[x][y] == 0) {
            return;
        }
        grid[x][y] = 0;
        // 探索新大陆
        dfs(grid, x+1, y, row, col); // 右
        dfs(grid, x-1, y, row, col); // 左
        dfs(grid, x, y+1, row, col); // 上
        dfs(grid, x, y-1, row, col); // 下
    }

    public static int getSum(int[][] grid) {
        if (grid == null) {
            return 0;
        }
        int[][] directions = new int[][]{{0,1}, {0, -1}, {1, 0}, {-1, 0}};
        int row = grid.length;
        int col = grid[0].length;
        int waters = 0;
        UnionFind uf = new UnionFind(row * col);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 0) {
                    waters++;
                } else {
                    for (int[] dir : directions) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x >= 0 && y >= 0 && x < row && y < col && grid[x][y] == 1) {
                            uf.union(x*col+y, i*col+j);
                        }
                    }
                }
            }
        }
        return uf.count - waters;
    }
}
